package com.liang.leetcode.stack;

import java.util.Stack;

/**
 * 32.最长有效括号
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 */
public class Stack02_LongestValidParentheses {
    public static void main(String[] args) {
        String s = "())((())";
        System.out.println(longestValidParentheses(s));
    }

    /**
     * 解法 1：栈
     */
    public static int longestValidParentheses(String s) {
        int maxLen = 0;
        // 用栈记录括号的索引位置
        Stack<Integer> stack = new Stack<>();
        // -1 入栈，表示最长子串从 0 开始
        stack.push(-1);
        for (int i = 0; i < s.length(); i++) {
            // 左括号直接入栈
            if (s.charAt(i) == '(') {
                stack.push(i);
            } else {
                // 右括号，弹出栈顶元素，判断是否匹配
                stack.pop();
                // 栈为空，表示没匹配上，将当前右括号索引位置压入栈中，更新起始位置
                if (stack.isEmpty()) {
                    // 后续最长子串，从 i 开始
                    stack.push(i);
                } else {
                    // 栈不为空，匹配成功，计算当前有效括号子串的长度，更新最长有效括号长度
                    maxLen = Math.max(maxLen, i - stack.peek());
                }
            }
        }
        return maxLen;
    }

    /**
     * 解法 2：动态规划
     */

}
